/*
 * @lc app=leetcode.cn id=207 lang=java
 *
 * [207] 课程表
 */

// @lc code=start

import java.util.Queue;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        
        int[] indegrees = new int[numCourses];  // 入度数组
        List<List<Integer>> adjacency = new ArrayList<>();  // 邻接表
        Queue<Integer> queue = new LinkedList<>();  // 队列

        for(int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        for(int[] cp : prerequisites) {
            indegrees[cp[0]]++;     // 构建入度数组---入度就是有多少个前驱课程
            adjacency.get(cp[1]).add(cp[0]);    // 构建邻接表---邻接表存储的是当前课程的后继课程
        }

        for(int i = 0; i < numCourses; i++) {
            if(indegrees[i] == 0) {
                queue.add(i);   // 将入度为0的课程加入队列
            }
        }

        while(!queue.isEmpty()) {
            int pre = queue.poll();     // 取出队首课程
            numCourses--;   // 课程数减一
            for(int cur : adjacency.get(pre)) {
                if(--indegrees[cur] == 0) {
                    queue.add(cur);     // 当入度为0时，加入队列
                }
            }
        }
        return numCourses == 0;
    }
}
// @lc code=end

